package weekMatch.one_346;

import java.util.*;

public class LeeCode_04_failed {
    public static void main(String[] args) {
//        for (int[] ints : modifiedGraphEdges(5, new int[][]{{4, 1, -1}, {2, 0, -1}, {0, 3, -1}, {4, 3, -1}}, 0, 1, 5)) {
//            System.out.print(Arrays.toString(ints));
//        }
        for (int[] ints : modifiedGraphEdges(5, new int[][]{{1,3,10},{4,2,-1},{0,3,7},{4,0,7},{3,2,-1},{1,4,5},{2,0,8},{1,0,3},{1,2,5}}, 3, 4, 11)) {
            System.out.print(Arrays.toString(ints));
        }
    }
    private static int[][] modifiedGraphEdges(int n, int[][] edges, int source, int destination, int target) {
        int[][] grid = new int[n][n];
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int[] e = edges[i];
            map.put(e[0] + "," + e[1], i);
            map.put(e[1] + "," + e[0], i);
            grid[e[0]][e[1]] = e[2];
            grid[e[1]][e[0]] = e[2];
            if (e[2] == -1)
                e[2] = 1;
        }
        List<List<Integer>> all = new ArrayList<>();
        List<List<int[]>> chances = new ArrayList<>();
        Set<Integer> used = new HashSet<>();
        used.add(source);
        List<Integer> list = new ArrayList<>();
        list.add(source);
        dfs(all, list, grid, destination, target, 0, used, source, chances, new ArrayList<>());
        int m = all.size();
        int unit = 2 * 1000_000_000;
        for (int i = 0; i < m; i++) {
            int c = all.size();
            for (int j = 0; j < c; j++) {
                List<Integer> son = all.get(j);
                long sum = 0;
                for (Integer num : son) {
                    sum += num;
                }
                if (sum > target)
                    continue;

            }
        }
        return null;
    }
    private static void dfs(List<List<Integer>> all, List<Integer> list, int[][] grid, int dest, int target, long sum, Set<Integer> used, int now,List<List<int[]>> chances, List<int[]> chance){
        if (sum > target)
            return;
        if (now == dest) {
            all.add(list);
            chances.add(chance);
            return;
        }
        for (int next = 0; next < grid[now].length; next++) {
            if (used.contains(next))
                continue;
            if (grid[now][next] == -1){
                used.add(next);
                ArrayList<int[]> newC = new ArrayList<>(chance);
                newC.add(new int[]{now, next});
                dfs(all, new ArrayList<>(list), grid, dest, target, sum + 1, used, next, chances, newC);
                used.remove(next);
            }else if (grid[now][next] > 0){
                used.add(next);
                dfs(all, new ArrayList<>(list), grid, dest, target, sum + grid[now][next], used, next, chances, new ArrayList<>(chance));
                used.remove(next);
            }
        }
    }
}
